package com.notion.algorithms.datastructures;

public class MaxHeap<T extends Comparable<T>> {

	private int maxLength;
	private int currentLastIndex=-1;
	private final T[] array;
	private final int NEGATIVE_SEARCH_RESULT=-1;
	
	@SuppressWarnings("unchecked")
	public MaxHeap(int maxNoOfElements){
		this.maxLength = maxNoOfElements;
		array = (T[]) new Comparable[maxLength];
	}
	/**
	 * 
	 * @param element
	 * @return index of element in the array
	 */
	public void insert(T element){
		currentLastIndex++;
		if(currentLastIndex==maxLength)
			throw new IllegalArgumentException("Heap full");
		array[currentLastIndex]=element;
		//bubble up recursively till element is at correct place in hierarchy
		bubbleUpIfRequired(currentLastIndex);
	}
	/**
	 * 
	 * @param idx array in
	 * @return
	 */
	private void bubbleUpIfRequired(int idx){
		if(idx==0)
			return;
		int parentIdx = getParentIndex(idx);
		T parentNode = getNodeAtIndex(parentIdx);
		if(null==parentNode)
			return;
		if(array[idx].compareTo(parentNode)>0){
			swapElementAtIndex(idx, parentIdx);
			//check if further bubble up is needed at parent
			bubbleUpIfRequired(parentIdx);
		}
	}
	private void bubbleDownIfRequired(int idx){
		//reached last index, no possibility of any further bubbling down
		if(idx==currentLastIndex)
			return;
		int leftChildIdx = getLeftChildIndex(idx);
		int rightChildIdx = getRightChildIndex(idx);
		int probableSwapIdx = NEGATIVE_SEARCH_RESULT;
		
		//find the max of 2 childs and swap with it
		if(leftChildIdx==NEGATIVE_SEARCH_RESULT){
			probableSwapIdx = rightChildIdx;
		}
		else if(rightChildIdx==NEGATIVE_SEARCH_RESULT){
			probableSwapIdx=rightChildIdx;
		}
		else{
			T leftChild = getNodeAtIndex(leftChildIdx);
			T rightChild = getNodeAtIndex(rightChildIdx);
			if(leftChild.compareTo(rightChild)>0)
				probableSwapIdx = leftChildIdx;
			else
				probableSwapIdx = rightChildIdx;
			}
		T probableSwapNode = getNodeAtIndex(probableSwapIdx);
		if(probableSwapNode==null)
			return;
		T currentNode = getNodeAtIndex(idx);
		if(currentNode.compareTo(probableSwapNode)<0){
			swapElementAtIndex(idx, probableSwapIdx);
			bubbleDownIfRequired(probableSwapIdx);
		}
			
	}
	private T getNodeAtIndex(int idx){
		T node=null;
		if(!(idx>currentLastIndex||idx<0))
			node = array[idx];		
		return node;
	}
	private void swapElementAtIndex(int fIdx,int sIdx){
		T tmp = array[fIdx];
		array[fIdx]=array[sIdx];
		array[sIdx] = tmp;
	}
	/**
	 * 
	 * @param childIndex
	 * @return parent Node or null if no parent node exists
	 */
	@SuppressWarnings("unused")
	private T getParentNodeForIndex(int childIndex){
		int parentIdx = getParentIndex(childIndex);
		T parentNode=null;
		if(!(parentIdx==NEGATIVE_SEARCH_RESULT))
			parentNode = array[parentIdx];
		
		return parentNode;
	}
	@SuppressWarnings("unused")
	private T getLeftChildNodeForIndex(int parentIndex){
		int childIndex = getLeftChildIndex(parentIndex);
		T childNode=null;
		if(!(childIndex==NEGATIVE_SEARCH_RESULT))
			childNode = array[childIndex];		
		return childNode;
	}
	@SuppressWarnings("unused")
	private T getRightChildNodeForIndex(int parentIndex){
		int childIndex = getRightChildIndex(parentIndex);
		T childNode=null;
		if(!(childIndex==NEGATIVE_SEARCH_RESULT))
			childNode = array[childIndex];		
		return childNode;
	}
	private int getParentIndex(int childIndex){
		int parentIndex;
		if(childIndex==0)
			parentIndex=NEGATIVE_SEARCH_RESULT;
		else
			parentIndex=childIndex>>1;
		
		return parentIndex;
	}
	/**
	 * 
	 * @param parentIndex
	 * @return left Child index OR <code>NEGATIVE_SEARCH_RESULT</code>
	 * if no left child exists for this parent index
	 */
	private int getLeftChildIndex(int parentIndex){
		int probableChildIndex = parentIndex<<1;
		if(probableChildIndex > currentLastIndex || probableChildIndex==parentIndex)
			probableChildIndex=NEGATIVE_SEARCH_RESULT;
		return probableChildIndex;
	}
	/**
	 * 
	 * @param parentIndex
	 * @return left Child index OR <code>NEGATIVE_SEARCH_RESULT</code>
	 * if no left child exists for this parent index
	 */
	private int getRightChildIndex(int parentIndex){
		int probableChildIndex = (parentIndex<<1)+1;
		if(probableChildIndex > currentLastIndex || probableChildIndex==parentIndex)
			probableChildIndex=NEGATIVE_SEARCH_RESULT;
		return probableChildIndex;
	}
	
	public T extractMax(){
		if(currentLastIndex==-1)
			return null;
		//swap max node with min node.Min node will trickle down to its correct position via bubble down
		T element = (T)array[0];
		array[0]=array[currentLastIndex--];
		bubbleDownIfRequired(0);
		return element;
	}
	public int getCurrentSize(){
		return currentLastIndex+1;
	}
	
}
